/*!
 Temelia - Trie tree interface.

 Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#ifndef TRIE_H_
#define TRIE_H_

#include "platform.h"
#include "common.h"
#include "vector.h"

struct _trie_tree_t;
typedef struct _trie_tree_t *trie_tree_t;

/*
 * @brief Constructor - builds an empty trie storing a key given by the user.
 * Complexity O(1)
 *
 * @param User's key stored in trie's root
 */
DECLSPEC trie_tree_t trie_new(void *key);

/*
 * @brief Destructor - frees the memory occupied by a trie tree.
 * Complexity O(1)
 *
 * @param Trie
 */
DECLSPEC void trie_delete(trie_tree_t trie);

/*
 * @brief Returns the key stored in trie's root.
 * Complexity O(1)
 *
 * @param Trie
 */
DECLSPEC void *trie_get_key(trie_tree_t trie);

/*
 * @brief Returns the parent of current trie tree.
 * Complexity O(1)
 *
 * @param Trie
 */
DECLSPEC trie_tree_t trie_get_parent(trie_tree_t trie);

/*
 * @brief Returns the vector containing references to current trie's children.
 * Cast the pointer to vector_t.
 * Complexity O(1)
 *
 * @param Trie
 */
DECLSPEC void *trie_get_children(trie_tree_t trie);

/*
 * @brief Returns the child at a given index.
 * Complexity O(1)
 *
 * @param Trie
 * @param Index
 */
DECLSPEC trie_tree_t trie_get_child(trie_tree_t trie, int index);

/*
 * @brief Inserts a pair of (suffix, key) in the current trie.
 * Complexity O(strlen(suffix))
 *
 * @param Trie
 * @param Suffix
 * @param User's key
 */
DECLSPEC trie_tree_t trie_insert(trie_tree_t trie, char *suffix, void *key);

/*
 * @brief Searches a suffix in the current trie. It returns the associated key of
 * this suffix.
 * Complexity O(strlen(suffix))
 *
 * @param Trie
 * @param Suffix
 */
DECLSPEC void *trie_search(trie_tree_t trie, char *suffix);

/*
 * @brief Removes the pair of (suffix, key) from the current trie.
 * This function finds the node associated with the suffix and
 * removes all the nodes which parents store NULL key.
 * Complexity O(strlen(suffix))
 *
 * @param Trie
 * @param Suffix
 */
DECLSPEC void trie_remove(trie_tree_t trie, char *suffix);

/*
 * @brief Returns children number of trie.
 * Complexity O(1)
 *
 * @param Trie
 */
DECLSPEC int trie_get_children_number(trie_tree_t trie);

/*
 * @brief Checks if trie node is leaf.
 * Complexity O(1)
 *
 * @param Trie
 */
DECLSPEC int trie_is_leaf(trie_tree_t trie);

/*
 * @brief Checks if trie node is empty.
 * Complexity O(1)
 *
 * @param Trie
 */
DECLSPEC int trie_is_empty(trie_tree_t trie);

/*
 * @brief Iterates over the trie's components in preoder; key_handler should be
 * called with keys associated with the strings in ascending lexicographical order.
 * Complexity O(tree size)
 *
 * @param Trie
 * @param Pointer to handler function
 * @param Context
 */
DECLSPEC void trie_preorder(trie_tree_t trie,
		void key_handler(void *key, void *context), void *context);

/*
 * @brief Iterates over the trie's components in postorder; key_handler should be
 * called with keys associated with the strings in descending lexicographical order.
 * Complexity O(tree size)
 *
 * @param Trie
 * @param Pointer to handler function
 * @param Context
 */
DECLSPEC void trie_postorder(trie_tree_t trie,
		void key_handler(void *key, void *context), void *context);

/*
 * @brief Iterates over the trie's components in level order; key_handler should be
 * called with keys associated with the strings in ascending length order.
 * Complexity O(tree size)
 *
 * @param Trie
 * @param Pointer to handler function
 * @param Context
 */
DECLSPEC void trie_level_order(trie_tree_t trie, void key_handler(void *key,
		void *context), void *context);

#endif /* TRIE_H_ */
